package 全排列;

import java.util.*;

public class fullsort {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        if(len==0){
            return res;
        }
        Deque<Integer> path = new ArrayDeque<Integer>();
        boolean[] used = new boolean[len];
        dfs(nums,len,0,path,used,res);
        return res;

    }

    public List<List<Integer>> dfs(int[] nums,int len, int depth,Deque<Integer> path,boolean[] used,List<List<Integer>> res ){
        if(depth == len){
            res.add(new ArrayList<>(path));
        }
        for(int i=depth ; i<len ; i++){
            if(used[i]){
                continue;
            }
            path.addLast(nums[i]);
            used[i]=true;
            dfs(nums,len,depth+1,path,used,res);
            path.removeLast();
            used[i]=false;
        }
        return  res;
    }

}
